package org.example.top41_80;

import org.example.top40.ListNode;

public class main43 {
    //排序列表
    //输入：head = [4,2,1,3]
    //输出：[1,2,3,4]
    //思路：递归终止条件：空链表或单节点链表 返回head  多节点链表继续分解，直到满足终止条件。
    //找到中间点 并用pre断开 递归 合并两链表
    public static void main(String[] args) {
        ListNode head = ListNodeBuilder.builder();
        ListNode node=sortListNode(head);
        System.out.println(node.val+"->"+node.next.val+"->"+node.next.next.val);
    }

    private static ListNode sortListNode(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode head2=mid(head);
        head=sortListNode(head);
        head2=sortListNode(head2);
        return meregeTwoListNode(head,head2);
    }

    private static ListNode meregeTwoListNode(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode pre=dummy;
        while (head1!=null&&head2!=null){
            if(head1.val<=head2.val){
                pre.next=head1;
                head1=head1.next;
            }else {
                pre.next=head2;
                head2=head2.next;
            }
            pre=pre.next;
        }
        if(head1!=null){
            pre.next=head1;
        }else {
            pre.next=head2;
        }
        return dummy.next;
    }

    private static ListNode mid(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=head;
        while (fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        return slow;
    }
}
